// 步骤： 使用cur遍历一遍链表，找出list_max和最小值list_min
// 通过（最大值-最小值）/ 每个桶的大小，计算出桶的个数
// 定义数组buckets为桶，桶个数为buckets_count个
// 使用cur遍历一遍链表，将每个元素装入对应的桶中
// 对每个桶内元素单独排序
// 最后按照顺序将桶内的元素拼成新的链表，并返回


// 时间复杂度，O(n)
// 空间复杂度，O(n + m), m为桶的个数


const { LinkedList, ListNode } = require('../1. 链表基础/1. 建立线性链表')

function bucketSort(head, bucketSize = 5) {
    // 1. 计算出链表中最大值list_max和最小值list_main
    let list_max = head.val
    let list_min = head.val
    let cur = head
    while (cur) {
        if (cur.val < list_min) {
            list_min = cur.val
        }
        if (cur.val > list_max) {
            list_max = cur.val
        }
        cur = cur.next
    }

    // 2. 计算桶的个数并定义桶
    let bucket_count = Math.floor((list_max - list_min) / bucketSize) + 1

    let buckets = new Array(bucket_count).fill(0).map(_ => null)

    // 3. 将链表的节点值依次添加到对应桶中
    cur = head
    while (cur) {
        let index = Math.floor((cur.val - list_min) / bucketSize)
        insertion(buckets, index, cur.val)
        cur = cur.next
    }

    let dummy_head = new ListNode(-1)
    cur = dummy_head
    // 将元素依次出桶，并拼接成有序链表
    for (let i = 0; i < bucket_count; i++) {
        buckets[i] = mergeSort(buckets[i])
        while (buckets[i]) {
            cur.next = buckets[i]
            cur = cur.next
            buckets[i] = buckets[i].next
        }
    }

    return dummy_head.next

}

// 将链表节点值val添加到对应桶buckets[index]中
function insertion(buckets, index, val) {
    if (!buckets[index]) {
        buckets[index] = new ListNode(val)
        return
    }
    let node = new ListNode(val)
    node.next = buckets[index]
    buckets[index] = node
}

function mergeSort(head) {
    if (!head || !head.next) {
        return head
    }
    // 快慢指针找到中心链节点
    let slow = head
    let fast = head.next
    while (fast && fast.next) {
        slow = slow.next
        fast = fast.next.next
    }

    // 断开左右链节点
    let left_head = head
    let right_head = slow.next
    slow.next = null
    return merge(mergeSort(left_head), mergeSort(right_head))
}

function merge(left, right) {
    let dummy_head = new ListNode(-1)
    let cur = dummy_head
    while (left && right) {
        if (left.val <= right.val) {
            cur.next = left
            left = left.next
        } else {
            cur.next = right
            right = right.next
        }
        cur = cur.next
    }
    if (left) {
        cur.next = left
    } else {
        cur.next = right
    }

    return dummy_head.next
}

const linkList = new LinkedList([2, 5, 1, 6, 3, 4])
let res = bucketSort(linkList.head)
// let res = mergeSort(linkList.head)
console.log(res)